Trapping Rain Water: Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

Example: Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

对于这道灌水题，因为水只有在凹槽中才能储存，因此可以用左右两个指针，一个指着array最左端，一个指着array最右端，分别标记此时左右两端的高度lheight, rheight, 取两个值中的较小值，假设是lheight，这个高度便是我们的“灌水基调”，使这个bar的指针往中间移动，，指向下一个bar，当下一个bar高度小于当前“灌水基调”，那么这个位置是可以储存住水的，两者高度差就是灌水量，而若下一个bar高度大于当前”灌水基调“，那么我们更新lheight为当前bar的高度，进入下一次循环，划线部分重复，直到左右指针相交。

`

public class Solution {
/**
 * @param heights: an array of integers
 * @return: a integer
 */
public int trapRainWater(int[] heights) {
    // write your code here
    /* check if input is valid */
    int left = 0, right = heights.length-1, res = 0;
    if(heights == null || heights.length == 0){
        return res;
    }

    int leftHeight = heights[left];
    int rightHeight = heights[right];
    while(left < right){
        if(leftHeight < rightHeight){
            left++;
            if(heights[left] < leftHeight){
                res += leftHeight-heights[left];
            }else{
                leftHeight = heights[left];
            }
        }else{
            right--;
            if(heights[right] < rightHeight){
                res += rightHeight-heights[right];
            }else{
                rightHeight = heights[right];
            }
        }
    }

    return res;
}

`